/** 
* @file ordered_array.cpp
* Implementation of ordered array operations (inserting, creating, deleting)
* First version inspired from JamesM's kernel development tutotrials.
* It is similar to (though more simple than) Doug Lea's malloc
* which is used in the GNU C library.
*
* Copyrights 2010 Michal Saman, m.saman@designplus.cz.
* This source code is release under the Apache License 2.0.
* http://www.apache.org/licenses/LICENSE-2.0
*/

#include <env.h>
#include <string.h>
#include <stdint.h>
#include <lib/ordered_array.h>
#include <mem/allocator.h>

/**
* Standart less_than routine, used if no special routine is need to keep entries ordered.
*/
int8_t std_lessthan(type_t a, type_t b) {
	return (a<b)?1:0;
}

/** 
* Function creates ordered array on specified address in memory.
* @param addr Address where to store entries of array.
* @param max_size Maximum count of entries of array.
* @param less_than Pointer to routine for ordering entries. If zero, use std_lessthan().
*/
ord_array_t ord_array_create(void* addr, uint32_t max_size, lessthan_t less_than) {
	ord_array_t ret_array;
	ret_array.entries = (type_t*)addr;
	ret_array.size = 0;
	memset(addr, 0, max_size*sizeof(type_t));
	ret_array.max_size = max_size;
	if (less_than)
		ret_array.less_than = less_than;					// use user less than predicate
	else
		ret_array.less_than = &std_lessthan;				// use std less than predicate
	return ret_array;
}

void ord_array_destroy(ord_array_t *ord_array) {
	// not implemented, yet :)
	//kfree(ord_array->entries);
}

/**
* Function for inserting new item to ordered array.
* @param item Pointer to item to insert.
* @param ord_array Array which to insert new item.
* @returns true/false due to success of inserting operation.
*/
bool ord_array_insert(type_t item, ord_array_t *ord_array) {

	if (!ord_array->less_than)							// no less_than comparator found
		return false;
	if (ord_array->size==ord_array->max_size)			// array is full
		return false;
	uint32_t i = 0;

	// iterate array until we find first same or larger entrie than our insered
	while (i < ord_array->size && ord_array->less_than(ord_array->entries[i], item)) {
		i++;
	}

	if (i==ord_array->size) {			// we are at end, just inset into size of array
		ord_array->entries[i] = item;
		ord_array->size++;
		//kprintf("Hole at: 0x%x (size: %i b), inserted at position %i\n", item, ((header_t*)ord_array->entries[i])->size, i);
	} else {							// insert item of current pos. and move all items after it.
		//kprintf("Hole at: 0x%x, position to insert %i\n", item, i);
		type_t tmp_item = ord_array->entries[i];
		ord_array->entries[i] = item;
		while (i < ord_array->size) {
			i++;
			type_t tmp_item2 = ord_array->entries[i];
			ord_array->entries[i] = tmp_item;
			tmp_item = tmp_item2;
		}
		//kprintf("Last item size: %u\n", ((header_t*)ord_array->entries[i])->size);
		ord_array->size++;
	}
	return true;
}

/**
* Function for deleting item from specified ordered array.
* @param i Position index of entrie to delete within array.
* @param ord_array Array from we want delete item.
* @returns true/false due to success of deleting operation.
*/
bool ord_array_delete(uint32_t i, ord_array_t *ord_array) {
	if (i >= ord_array->size)		// Position index is out of out array.
		return false;

	ord_array->size--;

	while (i < ord_array->size) {
		ord_array->entries[i] = ord_array->entries[i+1];
		i++;
	}

	return true;
}

/**
* Function lookup item at specified index position.
* @param i Index position to ordered array entries.
* @parama ord_array Pointer to ordered array.
*/
type_t ord_array_lookup(uint32_t i, ord_array_t *ord_array) {
	if (i >= ord_array->size)
		return NULL;
	return ord_array->entries[i];
}
